package MapAndSet;

import java.util.*;

class Student{

    public  String name;
    public  int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}
public class Test {

    //前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        //统计每个单词出现数量
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //2.创建小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    o1.getKey().compareTo(o2.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //3.遍历map
        for (Map.Entry<String,Integer> entry:map.entrySet()){
            if (minHeap.size()<k){
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue())<0){
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue())==0) {
                    if (top.getKey().compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        ArrayList <String> list = new ArrayList<>();
        for (int i=0;i<k;i++){
            Map.Entry<String ,Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }
        Collections.reverse(list);
        return list;
    }

    //坏键盘打字
    public static  void fun(String str1,String str2){
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        HashSet<Character> setGood = new HashSet<>();
        for (int i = 0; i <str2.length() ; i++) {
            char ch = str2.charAt(i);
            setGood.add(ch);
        }
        HashSet<Character> setBroken= new HashSet<>();
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if (! setGood.contains(ch)&& !setBroken.contains(ch)){
                setBroken.add(ch);
                System.out.print(ch);
            }
        }
    }

    public static void main(String[] args) {

        fun("7_This_is_a_test","_hs_s_a_es");
    }

    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            set.add(ch);
        }
        int count =0;
        for (int i=0;i<stones.length();i++){
            char ch = stones.charAt(i);
            if (set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
//随机链表的复制
public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur !=null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur =cur.next;
        }
        cur = head;
        while (cur !=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
}

    //只出现一次的数字
    //方法一：位运算
    public int singleNumber(int[] nums) {
        int c =0;
        for (int n:nums){
            c^=n;
        }
        return c;
    }
    //使用集合的方式
    public int singleNumber1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                set.remove(nums[i]);
            }else {
                set.add(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                return nums[i];
            }
        }
        return 0;
    }

    public  static Map<String,Integer>countWord(String[] words){
        Map<String,Integer>map = new HashMap<>();
        for (String s: words){
            if (map.get(s)==null){
                map.put(s,1);
            }else {
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        return  map;
    }
    public static void main8(String[] args) {
        String[] words = {"girl","you","know","i","want","your","love","girl","your","love",};
        Map<String,Integer> map = countWord(words);
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        for (Map.Entry<String,Integer>entry:entrySet){
            System.out.println("key:"+entry.getKey()+" val:"+entry.getValue());
        }

    }
    public static void main7(String[] args) {
        Student student1 = new Student("nan",18);
        Student student2 = new Student("xing",19);
        HashBuck2<Student,String> buck = new HashBuck2<>();
        buck.put(student1,"1234");
        buck.put(student2,"1344");
        System.out.println(buck.getVal(student1));
    }
    public static void main6(String[] args) {
        HashBuck buck = new HashBuck();
        buck.put(12,1212);
        buck.put(13,1313);
        buck.put(14,1414);
        buck.put(4,4444);
        buck.put(2,2222);
        buck.put(3,3333);
        buck.put(6,6666);
        buck.put(16,1616);
    }
    public static void main5(String[] args) {
        //找到这组数据中，第一个重复的数字
        int[] array ={1,2,2,3,3,4,5,6,7,8,9,12,1,8,7,9,6,5,4,13,16,53,66};
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (! set.contains(array[i])){
                set.add(i);
            }else {
                System.out.println(array[i]);
                return;
            }
        }
        //去除重复的数字
        /*int[] array ={1,2,2,3,3,4,5,6,7,8,9,12,1,8,7,9,6,5,4,13,16,53};
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);*/
    }
    public static void main4(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("nan");
        set.add("xing");
        set.add("tao");
        set.add("jv");
        System.out.println(set.size());
        System.out.println(set);
        System.out.println(set.contains("nan"));
        System.out.println(set.contains("yi"));
        System.out.println(set.contains("xing"));
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
        System.out.println();
    }
    public static void main3(String[] args) {
        Map<String,String> map = new TreeMap<>();
        map.put("齐天大圣","孙悟空");
        map.put("灌江口话事人","杨戬");
        map.put("双花红棍","哪吒");
        map.put("未来佛","弥勒");
       String  str = map.put("现在佛","如来");
        System.out.println(map.size());//5
        System.out.println(map.get("齐天大圣"));//孙悟空
        System.out.println(map.getOrDefault("双花红棍","哪吒"));//哪吒
        System.out.println(map.containsKey("未来佛"));//true
        System.out.println(map.containsValue("杨戬"));//true
        for (String s: map.keySet()){
            System.out.print(s+" ");//双花红棍 未来佛 灌江口话事人 现在佛 齐天大圣
        }
        System.out.println();
        System.out.println("========");
        for (String s: map.values()){
            System.out.print(s+" ");//哪吒 弥勒 杨戬 如来 孙悟空
        }
        System.out.println();
        System.out.println("======");
        for (Map.Entry<String,String>entry:map.entrySet()){
            System.out.println(entry.getKey()+"---->"+entry.getValue());
        }
        System.out.println();
    }
    public static void main2(String[] args) {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("nan",3);
        treeMap.put("jia",9);
        treeMap.put("ma",5);
        Integer ret =  treeMap.get("nan");
        System.out.println(ret);
        Integer val = treeMap.get("nan");
       Integer n =  treeMap.getOrDefault("nan",3);
        System.out.println(n);
        Set<Map.Entry<String,Integer>> entrySet = treeMap.entrySet();
        for (Map.Entry<String,Integer>entry: entrySet){
            System.out.println("key:"+entry.getKey()+" val "+entry.getValue());
        }
        Set<String> set = treeMap.keySet();
        treeMap.values();
    }
    public static void main1(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(2);
        bst.insert(9);
        BinarySearchTree .TreeNode ret = bst.search(9);
        System.out.println(ret.val);
        bst.remove(5);
    }
}
